The present invention relates to image coding and decoding apparatuses and, more specifically, to singular value decomposition image coding and decoding apparatuses.
In transmitting or storing image information, it is a general procedure to code the image information to reduce a data amount. Some of the presently available image coding techniques will be described below.
The orthogonal transform coding is performed, for instance, in the following manner:
a) Preliminarily setting a transform matrix A of, for instance, discrete cosine transform or Hadamard transform.
b) Dividing an image into blocks each of which consists of n.times.n pixels (n: integer equal to or greater than 2), that is, is represented by an n-row, n-column matrix X.
c) Performing an orthogonal transform on a block-by-block basis such that EQU Y=AXA.sup.T ( 1)
where A is an orthogonal matrix and A.sup.T is a transpose of A.
d) Coding n.sup.2 transform coefficients of Y on a block-by-block basis.
In this example, coding is performed by utilizing the fact that the power is concentrated in particular transform coefficients, for instance, by changing the number of levels for quantizing each transform coefficient in accordance with the magnitude of its power. Therefore, the coding efficiency is higher when the degree of the power deviation is larger. However, in general, since statistical properties of image information are different from one position to another, it is not always the case that image information has a large degree of power deviation. As a result, there exits a certain limit in improving the coding efficiency with the use of a single preset transform matrix.
In the Karhunen-Loeve transform coding, to accommodate a positional variation of statistical properties of an image, images having similar properties are grouped into a class, and an optimum transform matrix is used for each class. The Karhunen-Loeve transform coding is performed, for instance, in the following manner:
a) Dividing an image into blocks each of which consists of n.times.n pixels, that is, is represented by an n-row, n-column matrix X.
b) Grouping the blocks into classes.
c) Determining a vertical transform matrix Ay and a horizontal transform matrix Ax for each class.
d) Coding the transform matrices Ay and Ax having 2n.sup.2 elements for each class.
e) Performing an orthogonal transform for each block in accordance with the class to which the block belongs to, such that EQU Y=A.sub.y XA.sub.x.sup.T. (2)
f) Coding n.sup.2 transform coefficients of Y for each block.
In this example, as the number of classes increases, the power is more concentrated in particular transform coefficients and, therefore, the coding efficiency of the transform coefficients is improved. However, this will cause an increase in the number of transform matrices, which should also be coded. The extreme case is such that transform matrices are determined for each block, in which case n.sup.2 transform coefficients and transform matrices having 2n.sup.2 elements per block need to be coded.
The singular value decomposition coding is described in H. C. Andrews and C. L. Patterson, "Singular Value Decomposition (SVD) Image Coding," IEEE Transactions on Communications, Vol. COM-24, No. 4, pp. 425-432, April 1976 (referred to as reference (1) below). This coding method not only can accommodate a positional variation of statistical properties but also requires a relatively small number of items to be coded. The singular value decomposition coding is performed, for instance, in the following manner:
a) Dividing an image into blocks each of which consists of n.times.n pixels, that is, is represented by an n-row, n-column matrix X.
b) Performing singular value decomposition such that EQU X=U.sup.T GV (3)
In this equation, U and V are n-row, n-column orthonormal matrices, and EQU U.sup.T =[u.sub.1, . . . , u.sub.n ] (4) EQU V.sup.T =[v.sub.1, . . . , v.sub.n ] (5)
where each of u.sub.1, . . . , u.sub.n and v.sub.1, . . . , v.sub.n is a column vector of n rows. G is an n-row, n-column diagonal matrix whose diagonal elements are .gamma..sub.1, . . . , .gamma..sub.n.
c) Coding the n singular values .gamma..sub.1, . . . , .gamma..sub.n that have been obtained by the singular value decomposition.
d) Coding the 2n n-dimensional singular value vectors u.sub.1, . . . , u.sub.n and v.sub.1, . . . , v.sub.n that have also been obtained by the singular value decomposition.
In this example, since the power always concentrated in particular singular values, the coding can accommodate a positional deviation of statistical properties. Further, the number of items to be coded, 2n.sup.2 +n, is smaller than the number 3n.sup.2 in the case where the number of classes is maximum in the Karhunen-Loeve transform coding.
The singular value decomposition can be performed by determining eigenvalues and eigenvectors of X.sup.T X and XX.sup.T for the matrix X of a block consisting of n.times.n pixels. Since X.sup.T X and XX.sup.T are symmetric matrices, their eigenvalues and eigenvectors can be determined by a numerical calculation such as the Jacobi method. The amount of calculation for determining the matrices XX.sup.T, X.sup.T X, singular values .gamma..sub.1, . . . , .gamma..sub.n, and singular vectors u.sub.1, . . . , u.sub.n and v.sub.1, . . . , v.sub.n is on the order of 2(n.sup.3 +.alpha.) for each block. In the following, the amount of calculation is estimated in terms of the number of times of multiplications and additions. The above amount of calculation is larger than the amount of calculation, 2n.sup.3, of the orthogonal transform coding by 2.alpha.. This has been an obstruction to increasing the processing speed of a coding apparatus and decreasing its cost. The parameter .alpha. means an amount of convergence operations of the Jacobi method etc. For example, the amount of calculation of the Jacobi method varies depending on properties of the image block X, and is generally larger than that required for orthogonal transform. The parameter c is a ratio between the number of classes and the number of blocks.
Conventional methods of coding singular vectors include a method in which the elements of a singular vector are simply subjected to differential pulse coding modulation (DPCM), as in reference (1). Another example of coding singular vectors is described in N. Garguir, "Comparative Performance of SVD and Adaptive Cosine Transform in Coding Images," IEEE Transactions on Communications, Vol. COM-27, No. 8, pp. 1230-1234, August 1979 (referred to reference (2) below). In this method, the respective elements of a singular vector are normalized, then quantized by a Max quantizer, and finally transmitted in the form of fixed-length codes. The Max quantizer is described in J. Max, "Quantizing for Minimum Distortion," IEEE Trans. Inform. Theory, Vol. IT-6, No. 1, pp. 7-12, January 1960.
However, either method has a problem that singular vectors are not coded efficiently. The paper (in Japanese; referred to as reference (3) below) by Komatsu et al. entitled "Vector Quantization of Picture Signals by Singular Value Decomposition" in Shingakugiho, IE85-6, June 1985 discloses the use of vector quantization for effective coding of singular vectors. This method is still problematic in that the amount of calculation for vector quantization is large.
Conventional techniques of coding singular values described in literatures are only theoretical, and do not present any specific implementations in a coding apparatus.
As exemplified by references (2) and (3), there are conventional techniques of coding singular values and singular vectors in which the number of singular value and singular vector items to be transmitted is switched adaptively on a block-by-block basis in accordance with a positional variation of statistical properties of an image, and additional information indicating the number of items to be transmitted is also transmitted. In this case, although the image information itself is coded efficiently, the additional information is an obstruction to the improvement of the coding efficiency.
In the singular value decomposition coding method, the number of scalars of singular values and singular vectors to be coded and transmitted is 2n.sup.2 +n. This number is more than twice the number n.sup.2 of transform coefficients to be coded in the orthogonal transform coding method. This has been an obstruction to the improvement of the coding efficiency in the singular value decomposition coding method.